package cn.edu.jxau.test;

import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * 双向循环链表
 * 
 * @author Fudashi
 */
public class CyclicLinkedList<T> {

	private Node header;
	private int size;

	public CyclicLinkedList() {

		header = new Node(); // 空头节点
		header.next = header;
		header.previous = header;
	}

	public CyclicLinkedList(T[] arr) {
		this();
		addAll(size, arr);
	}

	public void addAll(int index, T[] arr) {

		// 参数校验 //
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException(String.format("index=%d，越界", index));
		}
		Objects.requireNonNull(arr, "参数arr不能为null");
		if (arr.length == 0) {
			return;
		}

		// 插入arr //
		Node successor = index == size ? header : node(index);
		Node predecessor = successor.previous;
		for (int i = 0; i < arr.length; i++) {
			Node node = new Node(predecessor, arr[i], successor);
			predecessor.next = node;
			predecessor = node;
		}
		successor.previous = predecessor;
		size += arr.length;
	}

	private Node node(int index) {

		// 参数校验 //
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException(String.format("index=%d越界，无指定节点", index));
		}

		// 遍历链表查找对应的节点 //
		Node cur = header;
		if (index < (size >> 1)) { // 链表的前半部分，从头开始遍历
			for (int i = 0; i <= index; i++) {
				cur = cur.next;
			}
		} else { // 链表的后半部分，从尾开始遍历
			for (int i = size; i > index; i--) {
				cur = cur.previous;
			}
		}
		return cur;
	}

	public T getFirst() {

		if (size == 0) {
			throw new NoSuchElementException("双向循环链表为空");
		}
		return header.next.data;
	}

	public T getLast() {

		if (size == 0) {
			throw new NoSuchElementException("双向循环链表为空");
		}
		return header.previous.data;
	}

	public T removeFirst() {

		if (size == 0) {
			throw new NoSuchElementException("双向循环链表为空");
		}
		return remove(header.next);
	}

	public T removeLast() {

		if (size == 0) {
			throw new NoSuchElementException("双向循环链表为空");
		}
		return remove(header.previous);
	}

	public void add(int index, T data) {

		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException(String.format("index=%d，越界", index));
		}
		Node successor = index == size ? header : node(index);
		addBefore(successor, data);
	}

	public void remove(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException(String.format("index=%d，越界", index));
		}
		Node node = node(index);
		remove(node);
	}

	public void addFirst(T data) {
		addBefore(header.next, data);
	}

	public void addLast(T data) {
		addBefore(header, data);
	}

	private Node addBefore(Node node, T data) {

		Node newNode = new Node(node.previous, data, node);
		newNode.previous.next = newNode;
		newNode.next.previous = newNode;
		size++;
		return newNode;
	}

	private T remove(Node node) {

		if (node == header) {
			throw new IllegalArgumentException("不可删除头结点");
		}
		T data = node.data;
		node.previous.next = node.next;
		node.next.previous = node.previous;
		node.next = null; // help GC
		node.previous = null;
		node.data = null;
		size--;
		return data;
	}

	public int indexOf(T data) {

		int index = 0;
		Node cur = header.next;
		if (data == null) { // 找第一个data为null的节点
			for (int i = 0; i < size; i++, index++) {
				if (cur.data == null) {
					return index;
				}
				cur = cur.next;
			}
		} else {
			for (int i = 0; i < size; i++, index++) {
				if (cur.data.equals(data)) {
					return index;
				}
				cur = cur.next;
			}
		}
		return -1;
	}

	private class Node {

		private Node previous;
		private T data;
		private Node next;

		public Node() {

		}

		public Node(Node previous, T data, Node next) {
			this.previous = previous;
			this.data = data;
			this.next = next;
		}
	}

	@Override
	public String toString() {

		StringBuilder builder = new StringBuilder();
		builder.append("size:").append(size).append("\t[");
		Node cur = header.next;
		for (int i = 0; i < size; i++) {
			builder.append(cur.data).append(",");
			cur = cur.next;
		}
		if (size > 0) {
			builder.deleteCharAt(builder.length() - 1);
		}
		builder.append("]");
		return builder.toString();
	}
}
